package q641_MyCircularDeque;

/*
这里的关键在于定义一个双向的链表结构 同时具有prev和next
每次插入和删除都取出对应的位置进行操作即可
 */
public class MyCircularDeque {
    ListNode head, tail;
    int size, capacity;
    public MyCircularDeque(int k) {
        size = 0;
        capacity = k;
        head = new ListNode(0);
        tail = new ListNode(0);
        head.next = tail;
        tail.prev = head;
    }

    public boolean insertFront(int value) {
        if (isFull()) return false;
        ListNode temp = head.next;
        head.next = new ListNode(value, head, temp);
        temp.prev = head.next;
        ++size;
        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()) return false;
        ListNode temp = tail.prev;
        tail.prev = new ListNode(value, temp, tail);
        temp.next = tail.prev;
        ++size;
        return true;
    }

    public boolean deleteFront() {
        if (isEmpty()) return false;
        ListNode temp = head.next;
        head.next = head.next.next;
        temp.prev = null;
        temp.next.prev = head;
        temp.next = null;
        --size;
        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()) return false;
        ListNode temp = tail.prev;
        tail.prev = tail.prev.prev;
        temp.next = null;
        temp.prev.next = tail;
        temp.prev = null;
        --size;
        return true;
    }

    public int getFront() {
        if (isEmpty()) return -1;
        return head.next.val;
    }

    public int getRear() {
        if (isEmpty()) return -1;
        return tail.prev.val;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

    class ListNode {
        int val;
        ListNode prev;
        ListNode next;

        public ListNode() {}
        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode prev, ListNode next) {
            this.val = val;
            this.prev = prev;
            this.next = next;
        }
    }
}
